#ifndef _TRIANGULATOR_H
#define _TRIANGULATOR_H

#include <iostream>
#include <vector>
#include "HeapPQueue.h"
#include "Triangle.h"
#include "Compare.h"
#include "Point.h"
#include "Edge.h"
// For random number
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

class Triangulator{

public:
	Triangulator(int width, int height, vector<Point*> points);
	~Triangulator();
	
	vector<Triangle*> getTriangles(); 
	//Jason's code, start with one triangle, then propagate its neighbour if needed
	void flip();
protected:
	HeapPQueue<Triangle*, TriangleCompare>* triangles;
	
	int width, height, numberOfPoints;
	int numOfTriangles;
	
	void addPoint(Point* newPoint);
	
	/*Create points on the four corners of the bounding rectangle
	 Draw a diagonal line across the point at (0, 0) and (width, height)
	 by creating two new triangles and inserting them into the heap
	 Returns false if dimension is invalid
	 */
	bool initializeBoundingRectangle(int width, int height);
	
	//Return false if the point coordinate is outside the dimension of the maze
	bool pointIsValid(Point* point);
	
	//Return true if p is inside t
	bool contains(Point* p, Triangle* t);
	
	//Return true if point1 connect to point2 connecting to point3 forms 
	//two lines in counter-clockwise direction
	int ccw(Point* point1, Point* point2, Point* point3);

//*****************************************************************************************************************************
	//Flip-associated functions:
	
	// Check if t is Delaunay with respect to neighbour
	bool isDelaunay(Triangle *t, Triangle *neighbor);

	// Check if p is contained in t
	bool isContained(Triangle *t, Point * p);

	// Check if p is inside the circumcircle of t
	bool isInsideCircumcircle(Triangle *t, Point* p);

	// create a 3-3-matrix
	// a,b,c form a triangle
	// d is any other point not inside triangle(a,b,c)

	// pre-condition: t1 and t2 are neighbour triangles
	// delete the line that t1 and t2 shared (one of the diagnal)
	// create two new triangles by joining the other diagnoal
	// assign the two new triangles to t1 and t2
	void reconstructTriangle(Triangle* &t1, Triangle* &t2);

	// iterate through all the triangles
	// for each triangle, set all its neighbour null
	void setAllNeighbourPointerNull();
	
	// iterate through all the triangles
	// for each triangle, find its neighbours and set neighbour pointer
	void resetNeighborPointer();
	
	// check if triangle(p1,p2,p3) are in counterclockwise orientation
	// if not, make it so
	void turnccw();


	// Helper functions:
	
	// create a 3-3-matrix
	// a,b,c form a triangle
	// d is any other point not inside triangle(a,b,c)
	int** createMatrix(Point *a, Point *b, Point *c, Point *d);

	// compute the determinant of a 3-3-matrix
	int det (int** m);

	// Check if p1 and p2 are the same point
	bool isTheSamePoint(Point *p1, Point *p2);

	// Check if t1 and t2 are the same triangle
	bool isTheSameTriangle(Triangle *t1, Triangle *t2);

	// store the heap triangles into a vector
	vector<Triangle*> copyTriangles();

        int numFlips;
};


#endif

